package algostruct

import (
	"iter"
	"sync"
)

// 线程安全队列
type Queue[T any] interface {
	//入队
	Enqueue(value T)
	//出队
	Dequeue() (T, bool)
	//判空
	IsEmpty() bool
	//迭代器 (Go 1.23+)
	Iter() iter.Seq[T]
}

type node[T any] struct {
	value T
	next  *node[T]
}

type queue[T any] struct {
	head  *node[T]
	tail  *node[T]
	mutex sync.Mutex
	cond  sync.Cond
}

// NewQueue creates a new empty queue
func NewQueue[T any]() Queue[T] {
	q := queue[T]{}
	q.cond = *sync.NewCond(&q.mutex)
	return &q
}

// Enqueue adds an item to the end of the queue
func (q *queue[T]) Enqueue(value T) {
	q.mutex.Lock()
	defer q.mutex.Unlock()

	node := &node[T]{value: value}
	if q.tail != nil {
		q.tail.next = node
	}
	q.tail = node

	if q.head == nil {
		q.head = node
	}
	q.cond.Signal()
}

// Dequeue removes and returns an item from the front of the queue
func (q *queue[T]) Dequeue() (T, bool) {
	q.mutex.Lock()
	defer q.mutex.Unlock()

	if q.head == nil {
		var zero T // return zero value for type T
		return zero, false
	}

	value := q.head.value
	q.head = q.head.next
	if q.head == nil {
		q.tail = nil
	}
	return value, true
}

func (q *queue[T]) IsEmpty() bool {
	q.mutex.Lock()
	defer q.mutex.Unlock()
	return q.head == nil
}

func (q *queue[T]) Iter() iter.Seq[T] {
	return func(yield func(T) bool) {
		q.mutex.Lock()
		values := make([]T, 0)
		for current := q.head; current != nil; current = current.next {
			values = append(values, current.value)
		}
		q.mutex.Unlock()
		for _, v := range values {
			if !yield(v) {
				return
			}
		}
	}
}
